class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        // 使用原始矩阵的第一行和第一列充当第二种方法中的set功能
        // 所以要处理第一行第一列存在 0 的情况
        bool rowZero = false, colZero = false;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(matrix[i][j] == 0)
                {
                    matrix[i][0] = matrix[0][j] = 0;
                    if(i == 0)
                        rowZero = true;
                    if(j == 0)
                        colZero = true;
                }
            }
        }

        // 从第二行第二列开始遍历
        for(int i = 1; i < n; i++)
        {
            for(int j = 1; j < m; j++)
            {
                if(matrix[i][0] == 0 || matrix[0][j] == 0)
                    matrix[i][j] = 0;
            }
        }

        for(int i = 0; rowZero && i < m; i++)
            matrix[0][i] = 0;
        for(int j = 0; colZero && j < n; j++)
            matrix[j][0] = 0;



        // 第二种方法
        // 下面这种时间复杂度为O(n + m)
        // set<int> x, y;
        // int n = matrix.size(), m = matrix[0].size();
        // for(int i = 0; i < n; i++)
        // {
        //     for(int j = 0; j < m; j++)
        //     {
        //         if(matrix[i][j] == 0)
        //         {
        //             x.insert(i);
        //             y.insert(j);
        //         }
        //     }
        // }
        // // 分别取出行和列置零
        // for(auto &e : x)
        //     for(int i = 0; i < m; i++)
        //         matrix[e][i] = 0;
        
        // for(auto &e : y)
        //     for(int j = 0; j < n; j++)
        //         matrix[j][e] = 0;



        // 第三种方法
        // 时间复杂度是O(n * m)
        // vector<vector<int>> t(matrix);
        // int n = matrix.size(), m = matrix[0].size();
        // for(int i = 0; i < n; i++)
        // {
        //     for(int j = 0; j < m; j++)
        //     {
        //         if(matrix[i][j] == 0)
        //         {
        //             for(int k = 0; k < m; k++)
        //                 t[i][k] = 0;
        //             for(int k = 0; k < n; k++)
        //                 t[k][j] = 0;
        //         }
        //     }
        // }
        // matrix = t;
    }
};